package day_7_8;

import java.util.HashMap;
import java.util.Map;

public class Main1 {
    /**
     * 146. LRU 缓存
     * https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked
     */
    class LRUCache {
        // 使用双向链表
        // 进行记录这个缓存的节点
        private static class Node {
            int key;
            int value;
            Node prev;
            Node next;

            Node(int key,int value){
                this.key = key;
                this.value = value;
            }
        }

        private int capacity;
        // 设置一个哨兵位的节点，防止节点的prev和next为空，简化代码
        private Node dummy = new Node(0,0);
        // 进行记录当前的缓存中是否存在对应的节点
        private Map<Integer,Node> hash = new HashMap<>();

        public LRUCache(int capacity) {
            this.capacity = capacity;
            dummy.prev = dummy;
            dummy.next = dummy;
        }

        public int get(int key) {
            Node node = getNode(key);
            return node != null ? node.value : -1;
        }

        public void put(int key, int value) {
            Node node = getNode(key); // 存在会将这个缓存放到前面
            if(node != null) {
                // 更新 value
                node.value = value;
                return;
            }
            node = new Node(key,value);
            hash.put(key,node);
            // 将这个node放到前面，新来的缓存就是最新使用的
            pushFront(node);
            // 判断是否超过缓存能存放的值，如果存在就删除缓存中最后的值
            if(hash.size() > capacity) {
                Node removeNode = dummy.prev;
                hash.remove(removeNode.key);
                remove(removeNode);
            }
        }

        // 每次获取对应的缓存呢，就需要将对应的缓存放到链表的头节点的位置上
        private Node getNode(int key) {
            if(!hash.containsKey(key)) {
                // 没有就直接返回
                return null;
            }
            // 存在就根据 hash 拿到缓存
            Node node = hash.get(key);
            remove(node); // 先将其在链表上删除
            pushFront(node); // 再将对应的节点放入到头结点位置上
            return node;
        }

        private void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void pushFront(Node node) {
            node.prev = dummy;
            node.next = dummy.next;
            node.prev.next = node;
            node.next.prev = node;
        }
    }
}
